package com.cqs.leetcode.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/16
 */
public class PowerSetLCCI {


    /**
     * 记录规模为n的数组结果集合的个数
     */
    private int[] cnt = null;

    public List<List<Integer>> subsets(int[] nums) {
        cnt = new int[nums.length + 1];
        cnt[0] = 1;
        Arrays.sort(nums);
        return subsets(nums, nums.length);
    }

    /**
     * 递归求解
     * @param nums  数组的
     * @param size 子数组个数
     * @return
     */
    private List<List<Integer>> subsets(int[] nums, int size) {
        List<List<Integer>> result = new ArrayList<>();
        if (size == 0) {
            result.add(new ArrayList<>());
            return result;
        }
        List<List<Integer>> subsets = subsets(nums, size - 1);
        //讲f(n-1)的结果集复制过来
        result.addAll(subsets);
        int i = 0;
        if (size > 1) {
            i = nums[size - 1] == nums[size - 2] ? cnt[size - 2] : 0;
        }
        for (; i < subsets.size(); i++) {
            //注意这里是复制数组
            List<Integer> list = new ArrayList<>(subsets.get(i));
            list.add(nums[size - 1]);
            result.add(list);
        }
        cnt[size] = result.size();
        return result;
    }

    public static void main(String[] args) {
        PowerSetLCCI power = new PowerSetLCCI();
        List<int[]> tests = new ArrayList<>();
        tests.add(new int[]{1, 2, 4, 2});
        tests.forEach(it -> {
            System.out.println(power.subsets(it));
        });

    }
}
